package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 回文子串的数目
    static class Solution {
        public int countSubstrings(String s) {
            int n = s.length();
            char[] nums = s.toCharArray();
            boolean[][] dp = new boolean[n][n];

            // 填表：i 倒序，j 正序
            for (int i = n-1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (nums[i] == nums[j]) {
                        // 首尾字符相等
                        if (i == j) {
                            dp[i][j] = true;  // 单字符
                        } else if (i+1 == j) {
                            dp[i][j] = true;  // 相邻字符
                        } else {
                            dp[i][j] = dp[i+1][j-1];  // 看内部
                        }
                    }
                    // 首尾不等，保持 false
                }
            }

            // 统计回文子串数量
            int ret = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {  // 只遍历上三角
                    if (dp[i][j]) ret++;
                }
            }

            return ret;
        }
    }
}